Theo các dữ liệu khảo cổ học, các cư dân đầu tiên tại lãnh thổ Primorsky là những người Cổ Á và Tungus. Họ gần như chắc chắn đã xuất hiện tại khu vực này vào khoảng 50-60 nghìn năm trước trong thời kỳ đồ đá cũ. Hậu duệ của các bộ lạc nói tiếng Tungus vẫn sinh sống tại Primorye và Priamurye cho đến ngày nay, họ là các dân tộc Nanai, Oroch và Udege.

Từ năm 698 đến 926, vương quốc Bột Hải tồn tại trên các vùng lãnh thổ ở phía bắc Triều Tiên, Mãn Châu và Primorsky, vương quốc này bao gồm những dân tộc Tungus bản địa và những người Cao Câu Ly mất nước. Bột Hải là một nhà nước phong kiến trung cổ tại Đông Á, và vương quốc đã phát triển về công nghiệp, nông nghiệp, chăn nuôi gia súc và có các truyền thống văn hóa và nghệ thuật riêng. Người dân Bột Hài duy trì các mối quan hệ về chính trị, kinh tế và văn hóa với nhà Đường và Nhật Bản.

Từ năm 1115 đến 1234, khu vực miền nam của Viễn Đông Nga ngày nay thuộc về một đế quốc hùng mạnh là nhà Kim của người Nữ Chân, một dân tộc Tungus. Chăn nuôi du mục phát triển và nông nghiệp trở thành nền tảng trong nền kinh tế của họ. Họ cũng phát triển một nền công nghiệp về luyện kim, đóng tàu và hàng xa xỉ. Nhà Kim có các chính sách đối ngoại và đối nội độc lập. Người Nữ Chân thiết lập quan hệ gần gũi với Nam Tống, Triều Tiên và Nhật Bản. Sau khi chinh phục miền bắc Trung Quốc, người Nữ Chân trở nên hưng thịnh cho đến khi bị người Mông Cổ xâm chiếm vào thế kỷ 13.

Nhà Kim sụp đổ dưới vó ngựa đội quân của Thành Cát Tư Hãn. Người Mông Cổ cho phá hủy các thành và cảng của Kim cùng với lực lượng hải quân Nữ Chân khá lớn. Phần lớn cư dân bị giết hoặc biến thành nô lệ, những người sống sót thì rút đến những vùng hoang vu. Uộc xâm lược của người Mông Cổ đã dẫn đến sự thay đổi vĩnh viễn về xã hội, văn hóa và kinh tế trong khu vực; số dân sư còn lại trong khu vực đã vĩnh viễn từ bỏ cuộc sống thành thị và tái định cư tại những vùng rừng núi hẻo lánh và các thung lũng sông Amur và Zabaykalye, cùng như dọc theo bờ biển Okho và nhiều phần trên đảo Sakhalin. Công nghiệp và ngành thủ công tinh xảo biến mất dần và kinh tế địa phương trở lại với việc đánh cá và săn bắn.

Nhà Minh đã chinh phục khu vực này trong thế kỷ 14.